"""
题目：给定单链表头节点和一个新值，在链表开头添加一个值为新值的节点，返回添加后的链表头节点（新节点成为新头）。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

"""在链表开头添加值为new_val的新节点，新节点成为新头"""
def prepend_node(head, new_val):
    # 步骤1：创建新节点，将其next指向原头节点
    new_node = ListNode(new_val, next=head)
    # 步骤2：新节点成为新的头节点
    return new_node


def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def traverse_linked_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
if __name__ == "__main__":
    # 测试1：非空链表添加
    head1 = create_linked_list([2, 3, 4])
    new_head1 = prepend_node(head1, 1)
    print(traverse_linked_list(new_head1))  # 输出: [1, 2, 3, 4]

    # 测试2：空链表添加
    head2 = create_linked_list([])
    new_head2 = prepend_node(head2, 0)
    print(traverse_linked_list(new_head2))  # 输出: [0]

    # 测试3：单节点链表添加
    head3 = create_linked_list([5])
    new_head3 = prepend_node(head3, 4)
    print(traverse_linked_list(new_head3))  # 输出: [4, 5]